def merge_sort(seq):  # 将一个大的数据结构拆分1分为2，2分为4，4分为8，每个分出去的再排序组成小的结构，再合并
    if len(seq) == 1:
        return seq
    else:
        mid = int(len(seq) / 2)
        seq_a = merge_sort(seq[:mid])
        seq_b = merge_sort(seq[mid:])
        new_seq = merge_sort_list(seq_a, seq_b)
        return new_seq


def merge_sort_list(seq_a, seq_b):
    a_length = len(seq_a)
    b_length = len(seq_b)
    a = 0
    b = 0
    new_seq = []
    while a < a_length and b < b_length:  # 从小到大排序
        if seq_a[a] < seq_b[b]:
            new_seq.append(seq_a[a])
            a += 1
        else:
            new_seq.append(seq_b[b])
            b += 1
    # a、b序列若有剩余则追加
    while a < a_length:
        new_seq.append(seq_a[a])
        a += 1
    while b < b_length:
        new_seq.append(seq_b[b])
        b += 1
    return new_seq


def test_merge_sort():
    seq = list(range(10))
    import random
    random.shuffle(seq)
    assert merge_sort(seq) == sorted(seq)
